package algorithm.leetcode.I201to400;

import java.util.Arrays;

/**
 * 区间合并
 * 最大上升子序列
 */

public class Q354 {

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, ((o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]));
        int maxLength = 1;
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果第j个信封可以套在第i个里面
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) dp[i] = Math.max(dp[i], dp[j]+1);
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

}
